package _11_整理题目._3_字符串_递归_dfs_bfs_双指针._子串子序列_最值;

import org.junit.Test;

import java.util.Arrays;

/**
 * https://leetcode-cn.com/problems/longest-increasing-subsequence/
 * https://www.nowcoder.com/practice/9cf027bf54714ad889d4f30ff0ae5481?tpId=117&&tqId=37796&rp=1&ru=/activity/oj&qru=/ta/job-code-high/question-ranking
 *
 * 给定数组arr，设长度为n，输出arr的最长递增子序列。
 * （如果有多个答案，请输出其中 按数值(注：区别于按单个字符的ASCII码值)进行比较的 字典序最小的那个）
 * 子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。
 * 例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
 *
 * 总思路：计算 最长递增子序列的 长度，再 找到 原序列
 *
 * 思路一：
 * 计算 最长递增子序列的长度：
 *      贪心 + 二分查找，时间 O(nlog(n))，空间 O(n)
 *      维护一个有序数组 arr，用于保存最长上升子序列，只是长度对，数组内容不一定对
 *      对原序列进行遍历，将每位元素二分插入 arr 中
 *          如果 数组 中元素都比它小，将它插到最后
 *          否则，用它覆盖掉比它 大的元素中最小的那个
 *              二分查找 左边界：比它大的元素中的最小的
 *          总之，思想就是让 数组 中存储比较小的元素
 * 找原序列：
 *      在计算最长递增子序列的长度的同时，维护一个 以 nums[i] 结尾的最长数组 res
 *
 * 思路二：动态规划，时间 O(n^2)，空间 O(n)
 *      定义：dp[i] 的值代表 nums 前 ii 个数字的最长子序列长度。
 *      初始状态：dp[i]dp[i] 所有元素置 11，含义是每个元素都至少可以单独成为子序列，此时长度都为 11。
 *      转移方程：
 *
 */
public class _041_最长递增子序列 {

    // 贪心二分 计算长度，更新找最小字典序
    public int[] lengthOfLIS(int[] nums) {
        int n = nums.length;
        int[] arr = new int[n];
        int[] maxLen = new int[n];
        int index = 0;  // 长度
        arr[index++] = nums[0];
        maxLen[0] = index;
        for (int i = 1; i < n; i++) {
            if (nums[i] > arr[index-1]) {
                arr[index++] = nums[i];
                maxLen[i] = index;
            } else {
                int left = 0, right = index-1;
                while (left <= right) {
                    int mid = left + (right-left) / 2;
                    if (nums[i] > arr[mid]) {
                        left = mid + 1;
                    } else if (nums[i] < arr[mid]) {
                        right = mid - 1;
                    } else {
                        right = mid - 1;
                    }
                }
                arr[left] = nums[i];
                maxLen[i] = left+1;
            }
        }

        int[] res = new int[index];
        for (int i=n-1, j=index; j>0; i--) {
            if (maxLen[i] == j) {
                res[--j] = nums[i];
            }
        }
        return res;
    }

    @Test
    public void main() {
        int[] nums = {1,2,8,6,4};
        System.out.println(Arrays.toString(lengthOfLIS(nums))); // 4
        System.out.println(lengthOfLIS1(nums)); // 4
    }

    // 动态规划 找长度
    public int lengthOfLIS1(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        Arrays.fill(dp, 1);
        int max = 1;
        for(int i=1; i<n; i++) {
            for(int j=0; j<i; j++) {
                if(nums[i] > nums[j]) {
                    dp[i] = Math.max(dp[i], dp[j]+1);
                }
            }
            max = Math.max(dp[i], max);
        }
        return max;
    }
}
